#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#define INIFITE 0x3f3f3f3f
#define MAX 105
#include <cstring>
typedef long long ll;
using namespace std;
int V[MAX];
int res[MAX];
int visited[MAX];
int e[MAX][MAX];
int n;
void Dijkstra(vector<vector<int> > Edge ) {
    memset(visited,0,sizeof(visited));
    for (int i=0; i<n; i++) res[i]=e[0][i];
    int pre,ma;
    while(1) {
        pre=-1;
        ma=INIFITE;
        for (int i=0; i<n; i++) {
            if (res[i]<ma && !visited[i]) {
                ma=res[i];
                pre=i;
            }
        }
        if (pre<0) break;
        visited[pre]=true;
        for (int i=0; i<Edge[pre].size(); i++) {
            if (e[0][pre] + e[pre][Edge[pre][i]] < e[0][Edge[pre][i]]) {
                e[0][Edge[pre][i]]=e[0][pre] + e[pre][Edge[pre][i]];
                res[Edge[pre][i]]=e[0][Edge[pre][i]];
            }
        }
    }
}
int main() {
    int a,b,c;
    int m;
    while (1) {
        scanf("%d%d", &n, &m);
        if (n==0) break;
        vector< vector<int> > Edge(n);
        memset(e,0x3f,sizeof(e));
        for (int i=0; i<m; i++) {
            scanf("%d%d%d",&a,&b,&c);
            a--; b--;
            Edge[a].push_back(b);
            e[a][b]=c;
            Edge[b].push_back(a);
            e[b][a]=c;
        }
        for (int i=0; i<n; i++) e[i][i]=0;
        Dijkstra(Edge);
        printf("%d\n", res[n-1]);
    }
    return 0;
}
